%----------------------------------------------------------------------------------------
%	PACKAGES AND DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[french,10pt,a4paper,oneside,notitlepage]{report}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=2.5cm]{geometry}
\usepackage[french]{babel}
\usepackage{xcolor}
\usepackage{times}
\usepackage{graphicx}
\usepackage{amsthm}
\usepackage{fourier}
\usepackage{hyperref}   % links im text
%\usepackage{enumerate}  % for advanced numbering of lists
\usepackage{fancyhdr}  
\usepackage{caption}
\usepackage{listings}
%\usepackage{mathtools}
\usepackage[protrusion=true,expansion=true]{microtype}
\makeatletter
\definecolor{bl}{rgb}{0,0.2,0.6}
\let\LaTeX@startsection\@startsection
\renewcommand{\@startsection}[6]{\LaTeX@startsection%
{#1}{#2}{#3}{#4}{#5}{\color{bl}\raggedright #6}}
\renewcommand{\thesection}{\@arabic\c@section}{\color{bl}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
  {-3.25ex\@plus -1ex \@minus -.2ex}%
  {1.5ex \@plus .2ex}%
  {\normalfont\normalsize\bfseries}}
\makeatother

\DeclareCaptionFont{white}{\color{white}}
\DeclareCaptionFormat{listing}{%
  \parbox{\textwidth}{\colorbox{gray}{\parbox{\textwidth}{#1#2#3}}}}
\captionsetup[lstlisting]{format=listing,labelfont=white,textfont=white}
\lstset{frame=lrb,xleftmargin=\fboxsep,xrightmargin=-\fboxsep}

\lstset{
 	language=C++,
% 	captionpos=b,
 	tabsize=3,
 	frame=single,
 	xleftmargin=\fboxsep,
 	xrightmargin=-\fboxsep,
 	keywordstyle=\color{blue},
 	commentstyle=\color{gray},
 	stringstyle=\color{green},
	extendedchars=true,
% 	numbers=left,
 	numberstyle=\tiny,
 	numbersep=5pt,
 	breaklines=true,
 	showstringspaces=false,
 	basicstyle=\footnotesize\ttfamily,
 	emph={label},
 	inputencoding=utf8,
 	extendedchars=true, 	
 	  literate=%
 	  {é}{{\'{e}}}1
 	  {è}{{\`{e}}}1
 	  {ê}{{\^{e}}}1
 	  {ë}{{\¨{e}}}1
 	  {û}{{\^{u}}}1
 	  {ù}{{\`{u}}}1
 	  {â}{{\^{a}}}1
 	  {à}{{\`{a}}}1
 	  {î}{{\^{i}}}1
 	  {ç}{{\c{c}}}1
 	  {Ç}{{\c{C}}}1
 	  {É}{{\'{E}}}1
 	  {Ê}{{\^{E}}}1
 	  {À}{{\`{A}}}1
 	  {Â}{{\^{A}}}1
 	  {Î}{{\^{I}}}1	
}
%
%\documentclass[12pt]{article}
%\usepackage[T1]{fontenc}
%\usepackage{lmodern}
%
%
%\usepackage{graphicx} % Required for the inclusion of images
%\usepackage{natbib} % Required to change bibliography style to APA
%\usepackage{amsmath} % Required for some math elements 
%\usepackage[margin=2.5cm]{geometry}
%\setlength\parindent{0pt} % Removes all indentation from paragraphs

%\renewcommand{\familydefault}{\sfdefault}
%\renewcommand{\labelenumi}{\alph{enumi}.} % Make numbering in the enumerate environment by letter rather than number (e.g. section 6)

%\usepackage{times} % Uncomment to use the Times New Roman font

%----------------------------------------------------------------------------------------
%	DOCUMENT INFORMATION
%----------------------------------------------------------------------------------------

\title{\textbf{Local consistencies}} % Title

\author{KHONG Minh Thanh} % Author name

\date{\today} % Date for the report

\begin{document}

%\maketitle % Insert the title, author and date
\begin{center}
\textbf{{\huge Local consistencies}}
\end{center}


%\begin{center}
%\begin{tabular}{l r}
%Partners: & KHONG Minh Thanh \\ % Partner names
%Instructor: & Professor Yves % Instructor/supervisor
%\end{tabular}
%\end{center}

% If you wish to include an abstract, uncomment the lines below
% \begin{abstract}
% Abstract text
% \end{abstract}

%----------------------------------------------------------------------------------------
%	SECTION 1
%----------------------------------------------------------------------------------------
\section{Local consistencies for binary constraints}
\subsection{Some general definitions}
	\begin{itemize}
	\item \textit{(i,j)-Consistency}
		\begin{itemize}
		\item[+] has non-empty domain
		\item[+] any consistent assignment of $i$ variables can be extended to a consistent assignment involving $j$ addition variables
		\end{itemize}
	\item \textit{Strong (i,j)-Consistency}
		\begin{itemize}
		\item[+] is $(k,j)$ consistent for all $k \leq i$
		\end{itemize}
	\item \textit{Path Consistency (2-Path Consistency)}
		\begin{itemize}
		\item[+] is $(2,1)$-consistent
		\end{itemize}
	\item \textit{Strong Path Consistency}
		\begin{itemize}
		\item[+] is \textbf{strong} $(2,1)$-consistent
		\end{itemize}
	\item \textit{m-Consistency}
		\begin{itemize}
		\item[+] is (m-1,1)-consistent
		\end{itemize}
	\item \textit{Strong m-Consistency}
		\begin{itemize}
		\item[+] is \textbf{strong} (m-1,1)-consistent
		\end{itemize}
	\end{itemize}

\subsection{Domain filtering consistencies}
\textbf{Definition}
	\begin{itemize}
	\item \textit{Restrict Path Consistency (RPC)}
		\begin{itemize}
		\item[+] A binary CSP $(X,D(X),C)$ is \textit{restricted path consistent} iff it is \textit{domain consistent} and 
		$\forall x_i \in X, \forall a \in D(x_i), \forall c_{ij}(x_i, x_j) \in C$ such that $(x_i,a)$ has a unique support $(x_j,b)$ on $c_{ij}(x_i, x_j)$, 
		
		$\forall x_k \in X$ linked to both $x_i, x_j$ by a constraint, there exists $c \in D(x_k)$ such that $c_{ik}(a,c) \wedge c_{jk}(b,c)$.
		\end{itemize}
	\item \textit{Path Inverse Consistency (PIC)}
		\begin{itemize}
		\item[+] A binary CSP $(X,D(X),C)$ is \textit{path inverse consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall x_j,x_k \in X$ there exists $b \in D(x_j), c \in D(x_k)$ such that $((x_i,a), (x_j,b), (x_k,c))$ is \textit{locally consistent}.
		\end{itemize}
		
	\item \textit{Max Restrict Path Consistency (Max-RPC)}
		\begin{itemize}
		\item[+] A binary CSP $(X,D(X),C)$ is \textit{max-restricted-path consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall c_{ij}(x_i,x_j) \in C$ there exists $b \in D(x_j)$ such that $c_{ij}(a,b)$ 
		
		and $\forall x_k \in X$ there exists $c \in D(x_k)$ with $((x_i,a), (x_j,b), (x_k,c))$ \textit{locally consistent}.
		\end{itemize}
		
	\item \textit{Neighborhood Inverse Consistency (NIC)}
		\begin{itemize}
		\item[+] A binary CSP $(X,D(X),C)$ is \textit{neighborhood inverse consistent} iff $\forall x_i \in X, \forall a \in D(x_i)$, the instantiation $(x_i, a)$ can be extended to a locally consistent instantiation on the set of all variables involved in a constraint with $x_i$.
		\end{itemize}
		
	\item \textit{Singleton Arc Consistency (SAC)}
		\begin{itemize}
		\item[+] A binary CSP $(X,D(X),C)$ is \textit{singleton arc consistent} iff $\forall x_i \in X, \forall a \in D(x_i)$, the subproblem $(X, D(X)_{x_i = a}, C)$ is \textit{domain consistent}.
		\end{itemize}
	\end{itemize}

\textbf{Comparison}
From \cite{domain:2001}, \cite{handbook:2005}

	\begin{figure}[ht]
	  	\begin{center}
		\includegraphics[height=2.8cm]{./images/comparison_consistency2.png}
		\caption{Summary of the comparison between domain-based consistencies.
%				 A $\rightarrow$ B means that local consistency A is strictly stronger than local consistency B. (The stronger relation is transitive.)}
		}
		\end{center}
	\end{figure}


We can find the complete proofs of the shema in \cite{domain:2001}.


%----------------------------------------------------------------------------------------
%	SECTION 2
%----------------------------------------------------------------------------------------
\pagebreak
\section{Local consistencies for non-binary constraints}
\subsection{Definition}

\textit{\textbf{Generalized Arc Consistency (GAC)}}
	\begin{itemize}
	\item[+] Definition: \\
	A CSP $(X, D(X), C)$ is \textit{generalized arc consistent} iff $\forall x_i \in X, D(x_i)$ is non-empty and $\forall a \in D(x_i), a$ is \textit{GAC-supported} in each constraint $c_j$, s.t. $x_i \in vars(c_j)$.\\
	A value $a \in D(x_i)$ is \textit{GAC-supported} in a constraint $c_j$ iff $\exists \tau \in rel(c_j)$ such that $\tau[x_i]=a$ and $\tau$ is valid. In this case, we say that $\tau$ is a \textit{GAC-support} of $a$ in $c_j$.
	
	\item[+] Algorithm:\\
	\textbf{GAC2001/3.1} time complexity: $O(ek^2d^k)$ space complexity: extensional constraint $O(ekd)$  \cite{domain:2008}
	
%	\item[+] Combine \textbf{PWC} with \textbf{GAC} we have: \textbf{PWC + GAC}. \cite{domain:2008}
	\end{itemize}


\subsection{Constraints-based}
\textit{\textbf{Constraint-based consistencies}}  \cite{domain:2008}

\textbf{Variables}
	\begin{itemize}
%	\item \textit{Relational Arc Consistency \textbf{(rAC)}}: \textbf{not presented}
%		\begin{itemize}
%		\item[+] Definition:\\
%		A CSP $(X, D(X), C)$ is \textit{relationally arc consistent} iff any consistent assignment for all but one of the variables in a constraint can be extended to the final variable so as to satisfy the constraint.
%		\end{itemize}
%	\item \textit{Relational Path Consistency \textbf{(rPC)}}: \textbf{not presented}
%		\begin{itemize}
%		\item[+] Definition:\\
%		A CSP $(X, D(X), C)$ is  \textit{relationally path consistent} iff any consistent assignment for all but one of the variables in a pair of constraints can be extended to the final variable so as to satisfy both constraints.
%		\end{itemize}
%	\item \textit{Relational m-Consistency}: \textbf{not presented}
%		\begin{itemize}
%		\item[+] Definition:\\
%		A CSP $(X, D(X), C)$ is \textit{relationally m-consistent} iff any consistent assignment for all but one of the variables in a set of $m$ distinct constraints can be extended to the final variable so as to satisfy all $m$ constraints.
%		\end{itemize}
	\item \textit{Relational (i,m)-Consistency}
		\begin{itemize}
		\item[+] Definition:\\
		A CSP $(X, D(X), C)$ is \textit{ relational (i,m)-consistent} iff any consistent assignment for $i$ variables in a set of $m$ constraints can be extended to all the variables in the set.
		\end{itemize}
	\item \textit{\textbf{Strong} Relational (i,m)-Consistency}
		\begin{itemize}
		\item[+] Definition:\\
		A CSP $(X, D(X), C)$ is \textit{\textbf{strong} relational (i,m)-consistent} iff 
		it is relational (j,m)-consistent for every $j \leq i$.
		\end{itemize}
	\end{itemize}

\textbf{Constraints}
	\begin{itemize}
	\item \textit{Pairwise Consistency \textbf{(PWC)}}
		\begin{itemize}
		\item[+] Definition:\\
		A CSP $(X, D(X), C)$ is \textit{pairwise consistent} iff it has non-empty relations and any consistent tuple $\tau$ of a constraint $c$ can be consistently extended to any other constraint that intersects with $c$.
		\end{itemize}
	\item \textit{k-Wise Consistency \textbf{(kWC)}}
		\begin{itemize}
		\item[+] Definition:\\
		A CSP $(X, D(X), C)$ is \textit{k-wise consistent} iff any consistent tuple for a constraint can be consistently extended to any $k-1$ other constraints.
		\end{itemize}	
%	\item \textit{Hyper-m-Consistency}: \textbf{not presented}
%		\begin{itemize}
%		\item[+] Definition:\\
%		A CSP $(X, D(X), C)$ is \textit{hyper-m-consistent} iff any consistent combination of tuples for $m - 1$ constraints can be consistently extended to
%		any \textit{m}th constraint.
%		\end{itemize}
	\end{itemize}
	
%----------------------------------------------------------------------------------------
\subsection{Domain-based}

\textit{\textbf{Domain-based consistencies}}
\begin{itemize}
	\item \textit{Restricted Pairwise Consistency \textbf{(RPWC)}}
		\begin{itemize}
		\item[+] Definition: \\
		A non-binary CSP $(X, D(X), C)$ is \textit{restricted pairwise consistent} iff $\forall x_i \in X,$ all values in $D(x_i)$ is GAC and, $\forall a \in D(x_i), \forall c_j \in C,$ $x_i \in vars(c_j),$ s.t. there exists a unique valid $\tau \in rel(c_j)$ with $\tau[x_i] = a,$\\
		$\forall c_k \in C,$ s.t. $vars(c_j) \cap vars(c_k) \neq \emptyset,$ $\exists \tau' \in rel(c_k),$ s.t. $\tau[vars(c_j) \cap vars(c_k)]= \tau'[vars(c_j) \cap vars(c_k)]$ and $\tau'$ is valid.
		\item[+] Algorithms:\\
		\textbf{RPWC-1} time complexity: $O(ne^2k^2d^k)$ space complexity: extensional constraint $O(ekd)$  \cite{domain:2008}
		\end{itemize}
		
	\item \textit{Relational Path Inverse Consistency \textbf{(rPIC)}}: also is \textit{Relational (1,2)-Consistency}
		\begin{itemize}
		\item[+] Definition:\\
		A non-binary CSP $(X, D(X), C)$ is \textit{relational path inverse consistent} iff $\forall x_i \in X, \forall c_j \in C,$ where $x_i \in vars(c_j)$, and $\forall c_k \in C,$ s.t $vars(c_j) \cap vars(c_k) \neq \emptyset,$ $\exists \tau \in rel(c_j)$ such that $\tau[x_i]=a$, $\tau$ is valid, \textbf{and} $\exists \tau' \in rel(c_k)$ such that $\tau[vars(c_j)\cap vars(c_k)] = \tau'[vars(c_j)\cap vars(c_k)]$ and $\tau'$ is valid.
		
		\item[+] Algorithms:\\
	 	\textbf{rPIC-1}, time complexity: $O(e^2k^2d^p)$ space complexity: extensional constraint $O(e^2kd)$ \cite{domain:2008}
		\end{itemize}
		
	\item \textit{Max Restrited Pairwise Consistency \textbf{(Max-RPWC)}}
		\begin{itemize}
		\item[+] Definition: \\
		A non-binary CSP $(X, D(X), C)$ is \textit{max restricted pairwise consistent} iff $\forall x_i \in X,$ $\forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ such that $\tau[x_i]=a$, $\tau$ is valid, \textbf{and} $\forall c_k \in C,$ s.t. $vars(c_j) \cap vars(c_k) \neq \emptyset, \exists \tau' \in rel(c_k),$ s.t. $\tau[vars(c_j) \cap vars(c_k)]= \tau'[vars(c_j) \cap vars(c_k)]$ and $\tau'$ is valid.
		\item[+] Algorithms:\\
		\textbf{Max-RPWC-1} time complexity: $O(e^2k^2d^p)$ space complexity: extensional constraint $O(ekd)$ \cite{domain:2008} \\
		\textbf{Max-RPWC-2} time complexity: $O(e^2kd^k)$ space complexity: extensional constraint $O(e^2kd^f)$ \cite{domain:2008} \\
		\textbf{Max-RPWC-3} time complexity: $O(e^2k^2d^p)$ space complexity: extensional constraint $O(e^2kd)$ \cite{domain:2008}
		\end{itemize}
	\item \textit{Relational Neighborhood Inverse Consistent \textbf{(rNIC)}}
		\begin{itemize}
		\item[+] Definition:\\
		A CSP $(X, D(X), C)$ is \textit{relational neighborhood inverse consistent} iff 
		$\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ such that $\tau[x_i]=a, \tau$ is valid, \textbf{and} $\tau$ can be extended to a solution of the subproblem consisting of the set of variables $X_j= \{vars(c_j)\cup vars(c_{j_1})\cup\dots\cup vars(c_{j_m})\},$ where $c_{j_1},\dots,c_{j_m}$ are the constraints that intersect with $c_j$.
		\item[+] \textbf{rNIC} $\longrightarrow$ \textbf{MaxRPWC} \cite{strong domain:2008}
%		\textbf{rNIC} is incomparable to \textbf{Max-R3WC} \cite{strong domain:2008}
		\end{itemize}
	\item \textit{Singleton Generalized Arc Consistency (SGAC)}
	\begin{itemize}
		\item[+] Definition: \\
		A CSP $(X, D(X), C)$ is \textit{singleton generalized arc consistent} iff it has non-empty domain and for any assignment of a variable, the resulting subproblem can be made \textit{GAC} ($(X, D(X)_{x=a}, C)$ is \textit{GAC}).
	\end{itemize}
	
\end{itemize}



\textbf{\textit{Comparison of domain-based consistencies}}

Follow \cite{domain:2008}, we have a figure of comparison:

	\begin{figure}[ht]
	  	\begin{center}
		\includegraphics[height=1.5cm]{./images/comparison_non_binary.png}
		\caption{Summary of the comparison between domain-based consistencies for non-binary constraints}
		\end{center}
	\end{figure}
For the full proofs, we can find it in \cite{domain:2008}.

%----------------------------------------------------------------------------------------
\subsection{Other domain-based}
\textit{\textbf{Domain-based extentions}} \cite{strong domain:2008}
	\begin{itemize}
%	\item \textit{Relational (1,3)-Consistency}: extension of \textbf{rPIC}
%		\begin{itemize}
%		\item[+] Definition: \\
%		A CSP $(X, D(X), C)$ is \textit{relational (1,3)-consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j)$, and for each pair of constraints $c_k, c_l \in C$, there exists $\tau \in rel(c_j)$ such that $\tau[x_i]=a, \tau$ is valid, \textbf{and} $\tau' \in rel(c_k), \tau'' \in rel(c_l)$ s.t. $\tau[vars(c_j)\cap vars(c_k)] = \tau'[vars(c_j)\cap vars(c_k)], \tau[vars(c_j)\cap vars(c_l)]=\tau''[vars(c_j)\cap vars(c_l)], \tau'[vars(c_k)\cap vars(c_l)]=\tau''[vars(c_k)\cap vars(c_l)]$.
%		\item[+] \textbf{MaxR3WC} $\longrightarrow$ \textbf{r(1,3)C} $\longrightarrow$ \textbf{rPIC}
%		\end{itemize}
%	\item \textit{Relational (1,m)-Consistency}: extension of \textbf{rPIC}
%		\begin{itemize}
%		\item[+] Definition: \\
%		A CSP $(X, D(X), C)$ is \textit{relational (1,m)-consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j),$ and for any set of additional $k-1$ constraints $c_1, \dots, c_{k-1},$ there exists $\tau \in rel(c_j)$ such that $\tau[x_i]=a, \tau$ is valid, \textbf{and} $\tau$ can be extended to a valid instantiation on variables $\bigcup_{m=1}^{k-1}vars(c_m)$ that satisfies each $c_m$ for $m=1,\dots,k-1$.
%%		\item[+] Algorithms:\\ \textbf{non algo}
%		\end{itemize}
	\item \textit{Max Restricted 3-wise Consistency \textbf{(Max-R3WC)}}: extension of \textbf{Max-RPWC}
		\begin{itemize}
		\item[+] Definition: \\
		A CSP $(X, D(X), C)$ is \textit{max restricted 3-wise consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ such that $\tau[x_i]=a, \tau$ is valid, \textbf{and} $\forall c_k, c_l \in C$ there exists valid tuples $\tau' \in rel(c_k), \tau'' \in rel(c_l)$ s.t. $\tau[vars(c_j)\cap vars(c_k)] = \tau'[vars(c_j)\cap vars(c_k)], \tau[vars(c_j)\cap vars(c_l)]=\tau''[vars(c_j)\cap vars(c_l)], \tau'[vars(c_k)\cap vars(c_l)]=\tau''[vars(c_k)\cap vars(c_l)]$.
		\item[+] Algorithms:\\
		\textbf{R3WC-1} time complexity: $O(e^3k^3d^{p+p'})$ space complexity: extensional constraint $O(ekd)$ \cite{strong domain:2008}
		\item[+] \textbf{rNIC} is incomparable to \textbf{Max-R3WC} \cite{strong domain:2008}
		\end{itemize}
	\item \textit{Max Restricted k-wise Consistency \textbf{(Max-RkWC)}}: extension of \textbf{Max-RPWC}
		\begin{itemize}
		\item[+] Definition: \\
		A CSP $(X, D(X), C)$ is \textit{max restricted k-wise consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ such that $\tau[x_i]=a, \tau$ is valid, \textbf{and}
		for any set of additional $k-1$ constraints $c_1, \dots, c_{k-1}, \tau$ can be extend to a valid instantiation on variables $\bigcup_{m=1}^{k-1}vars(c_m)$ that satisfies each $c_m$ for $m=1,\dots,k-1$.
%		\item[+] Algorithms:\\ \textbf{non algo}
		\end{itemize}
	\end{itemize}

%\textit{\textbf{Other domain-based extentions}} \cite{strong inverse:2007} \cite{strong domain:2008}
%	\begin{itemize}
%%	\item \textit{Relational Neighborhood Inverse Consistent \textbf{(rNIC)}}
%%		\begin{itemize}
%%		\item[+] Definition:\\
%%		A CSP $(X, D(X), C)$ is \textit{relational neighborhood inverse consistent} iff 
%%		$\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ such that $\tau[x_i]=a, \tau$ is valid, \textbf{and} $\tau$ can be extended to a solotuion of the subproblem consisting of the set of variables $X_j= \{vars(c_j)\cup vars(c_{j_1})\cup\dots\cup vars(c_{j_m})\},$ where $c_{j_1},\dots,c_{j_m}$ are the constraints that intersect with $c_j$.
%%		\item[+] \textbf{rNIC} $\longrightarrow$ \textbf{MaxRPWC}
%%		
%%		\textbf{rNIC} is incomparable to \textbf{Max-R3WC} \cite{strong domain:2008}
%%		\end{itemize}
%	\item \textit{Pairwise Inverse Consistency \textbf{(PWIC)}}: \textbf{is it Max-RPWC?} \cite{Inverse:2006}
%		\begin{itemize}
%		\item[+] Definition: \\
%		A CSP $(X, D(X), C)$ is \textit{pairwise inverse consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j),$ $\exists \tau \in rel(c_j)$ such that $\tau[x_i]=a, \tau$ is valid, \textbf{and} $\forall c_k \in C,$ s.t. $vars(c_j)\cap vars(c_k) \neq \emptyset, \exists \tau' \in rel(c_k)$ s.t. $\tau[vars(c_j)\cap vars(c_k)]=\tau'[vars(c_j)\cap vars(c_k)]$ and $\tau'$ is valid
%		\item[+] Algorithms:\\
%		\textbf{PWIC-1} $O(e^2k^3d^{2k-f})$ \cite{Inverse:2006}\\
%		\textbf{PWIC-2} $O(e^2k^2d^{k})$ \cite{Inverse:2006}
%		
%		\item[+] \textbf{PWIC} $\longrightarrow$ \textbf{rPIC} \cite{Inverse:2006}
%		\end{itemize}
%
%	\item \textit{Inverse $\omega$-Consistency \textbf{(I$\omega$C)}}
%		\begin{itemize}
%		\item[+] Definition: 
%		\item[+] Algorithms:\\
%		\textbf{I$\omega$C-1} $O(e^3k^3d^{p})$ \cite{strong domain:2008}
%		\end{itemize}
%	\item \textit{Extended Inverse $\omega$-Consistency \textbf{(EI$\omega$C)}}
%		\begin{itemize}
%		\item[+] Definition: 
%		\item[+] Algorithms:\\
%		\textbf{EI$\omega$C-1} $O(e^3k^3d^{p+p'})$ \cite{strong domain:2008}
%		\end{itemize}
%	\item \textit{Domain k-Wise Consistency \textbf{(DkWC)}}: combine \textbf{k-Wise Consistency (kWC) with GAC} \cite{DkWC:2014}\\
%		O(?????????????????????????)
%
%	\end{itemize}



%----------------------------------------------------------------------------------------
%	BIBLIOGRAPHY
%----------------------------------------------------------------------------------------
%
%\bibliographystyle{apalike}
%
%\bibliography{sample}

\begin{thebibliography}{9}
\bibitem{materiel} Documents in the course
\bibitem{domain:2001} Debruyne, Romuald, and Christian Bessiére. "Domain filtering consistencies." J. Artif. Intell. Res. (JAIR) 14 (2001): 205-230.
\bibitem{handbook:2005} Bessiere, Christian. "Constraint propagation." Handbook of constraint programming (2006): 29-83.
\bibitem{domain:2008} Bessiere, Christian, Kostas Stergiou, and Toby Walsh. "Domain filtering consistencies for non-binary constraints." Artificial Intelligence 172.6 (2008): 800-822.
\bibitem{Inverse:2006} Stergiou, Kostas, and Toby Walsh. "Inverse Consistencies for Non-Binary Constraints." FRONTIERS IN ARTIFICIAL INTELLIGENCE AND APPLICATIONS 141 (2006): 153.

\bibitem{strong inverse:2007} Stergiou, Kostas. "Strong Inverse Consistencies for Non-Binary CSPs." Tools with Artificial Intelligence, 2007. ICTAI 2007. 19th IEEE International Conference on. Vol. 1. IEEE, 2007.

\bibitem{strong domain:2008} Stergiou, Kostas. "STRONG DOMAIN FILTERING CONSISTENCIES FOR NON-BINARY CONSTRAINT SATISFACTION PROBLEMS." International Journal on Artificial Intelligence Tools 17.05 (2008): 781-802.

%\bibitem{DkWC:2014} Mairy, Jean-Baptiste, Yves Deville, and Christophe Lecoutre. "Domain k-Wise Consistency Made as Simple as Generalized Arc Consistency." 11th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2014). 2014.
\end{thebibliography}


%----------------------------------------------------------------------------------------


\end{document}